//
// Created by Administrator on 2020/10/28.
//

#ifndef GRAPH_BASIC_DENSEGRAPH_H
#define GRAPH_BASIC_DENSEGRAPH_H
#include <iostream>
#include <vector>
#include <cassert>
using namespace  std;

class DenseGraph{
private:
    int n, m;      // 节点数和边数
    bool directed; // 是否是有向图
    vector<vector<bool>> g;
public:
    DenseGraph(int n, bool directed){
        this->n = n;
        this->m = 0;
        this->directed = directed;
        for(int i = 0; i < n; i++){
            g.push_back(vector<bool>(n, false));
        }
    }
    ~DenseGraph(){};
    int V(){ return n;} // 图的顶点总数
    int E(){ return m;} // 图的边总数
    // 增加节点v与节点w之间的一条边
    void addEdge(int v, int w){
        assert(v >= 0 && v < n);
        assert(w >= 0 && w < n);
        if(hasEdge(v, w)) return; // 处理了平行边，并且防止边数m多加一次
        g[v][w] = true;
        if(!directed) // 如果是无向图
            g[w][v] = true;
        m++;
    }
    bool hasEdge(int v, int w){
        assert(v >= 0 && v < n);
        assert(w >= 0 && w < n);
        return g[v][w];
    }
    void show(){

        for( int i = 0 ; i < n ; i ++ ){
            cout<<"vertex "<<i<<":\t";
            for( int j = 0 ; j < g[i].size() ; j ++ )
                cout<<g[i][j]<<" ";
            cout<<endl;
        }
    }
    // 迭代器实现
    // 顶点的邻边按顺序输出
    class adjIterator{
    private:
        DenseGraph &G;
        int index; // 遍历到的节点坐标
        int v;
    public:
        adjIterator(DenseGraph &graph, int v):G(graph){
            this->v = v;
            this->index = -1;
        }
        int begin(){
            index = -1;
            return next();
        }
        int next(){
            for(index += 1; index < G.V(); index++) {
                if(G.g[v][index]) // 如果v与index相连
                    return index;
            }
            return -1; // 没有邻边
        }
        bool end(){
            return index >= G.V();
        }
    };
};
#endif //GRAPH_BASIC_DENSEGRAPH_H
